{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# We start with procedures that are used to compute the vertex connectivity kappa_G(s,t) \n", "# and to display the kappa_G(s,t) internally disjoint s-t paths.\n", "# We follow the algorithm presented in \n", "# A.-H. Hossein, Connectivity Algorithms, \n", "# Chapter 12 in Topics in Structural Graph Theory, Beineke and Wilson eds., \n", "# Cambridge University Press, 2013\n", "\n", "def VertexNetwork(G,s,t): \n", "# For a graph G and vertices s and t, \n", "# defines a digraph in which a max flow from s to t is equal to kappa_G(s,t).\n", "# Vertices of G must be labelled {0,1,...,n-1}, where n is the order of G.\n", " V=set(G.vertices());\n", " U=list(V.difference({s,t}));\n", " n=G.order();\n", " H=G.subgraph(U);\n", " F=DiGraph();\n", " F.add_vertices([s,t]);\n", " E=H.edges();\n", " for v in U:\n", " F.add_vertices([v,v+n]);\n", " F.add_edge(v,v+n);\n", " for e in E:\n", " e1=e[0];\n", " e2=e[1];\n", " F.add_edge(e1+n,e2);\n", " F.add_edge(e2+n,e1);\n", " for v in U:\n", " if G.has_edge(s,v):\n", " F.add_edge(s,v);\n", " if G.has_edge(v,t):\n", " F.add_edge(v+n,t);\n", " if G.has_edge(s,t):\n", " F.add_edge(s,t);\n", " return F;\n", "\n", "def VertexConnectivity(G,s,t): # Computes kappa_G(s,t) \n", " n=G.order()\n", " H=VertexNetwork(G,s,t)\n", " F=H.flow(s,t,value_only=True)\n", " return F\n", "\n", "def InternallyDisjointPaths(G,s,t,SizeOfFigure): \n", "# Displays a drawing of G in which a collection of kappa_G(s,t) internally disjoint \n", "# paths is rainbow coloured.\n", "# Returns a list of lists containing the edges of each path.\n", "# SizeOfFigure=[x,y] is used when plotting G.\n", " n=G.order()\n", " H=VertexNetwork(G,s,t)\n", " F=H.flow(s,t,value_only=False)[1]\n", " for i in range(n):\n", " F.contract_edge(i,i+n)\n", " E=F.edges()\n", " P=[]\n", " for e in E:\n", " if e[0]==s:\n", " P.append([e])\n", "\n", " for p in P:\n", " while True:\n", " length=len(p)\n", " head=p[length-1][1]\n", " if head==t:\n", " break\n", " else:\n", " for e in E:\n", " if head==e[0]:\n", " p.append(e)\n", " \n", " NumPaths=len(P)\n", " \n", " for i in range(NumPaths):\n", " p=P[i]\n", " for e in p:\n", " G.delete_edge((e[0],e[1],None))\n", " G.delete_edge((e[1],e[0],None))\n", " G.add_edge((e[0],e[1],i+1))\n", " \n", " Colors={}\n", " Colors.update({None:\"black\"})\n", " R=rainbow(NumPaths+1)\n", " for i in range(NumPaths):\n", " Colors.update({i+1:R[i]})\n", " \n", " GP=G.graphplot(edge_labels=False, color_by_label=Colors)\n", " show(GP.plot(figsize=SizeOfFigure))\n", " print(\"Found\",NumPaths,\"internally disjoint paths between the vertices labelled\",s,\"and \"+str(t)+\".\")\n", " return P" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "def SubgraphOfPsi(k,l):\n", "# Returns a graph isomorphic to Psi_{k,p}[0,l-1], \n", "# assuming p>l+s so that edges don't \"wrap around\".\n", "# The vertices w_0 to w_{l-1} are labelled 0 to l-1, respectively.\n", "# The vertices x_0 to x_{l-1} are labelled l to 2l-1, respectively.\n", "# The vertices y_0 to y_{l-1} are labelled 2l to 3l-1, respectively.\n", "# The vertices z_0 to z_{l-1} are labelled 3l to 4l-1, respectively.\n", "\n", " E=[]\n", " for i in range(l):\n", " for j in range(k):\n", " if i+j